package substr

// A Finder divides a string into substrings.
// The second parameter is the maximum number of substrings to find. It may, at
//its discretion, return n+1 substrings where the (n+1)st is the remainder of
//the string.
// If the second paramter is less than 0, find all substrings.
// It is up to the author of a Finder to ensure that a valid *S is
//returned and that the passed in []byte is not modified.
type Finder interface {
	Find([]byte, int) *S
}

// Replace index i with a refinement of the matches of i described by the passed
//in finder. 
// No validation is done on the result of the returned function, hereafter r.
// If len(r)==0, the same as self.Delete(i). If len(r)==1, same as
//self.Set(i, r[0][0], r[0][1]). If len(r)>1, the indicies grows by len(r)-1 and
//self.Subs[i] "==" r[0] and so on for i + 1, i + 2, ..., i + len(r).
// The operation is inplace and returns itself for chaining.
func (s *S) Refine(i int, F Finder) *S {
	ao, bo := s.Subs[i][0], s.Subs[i][1]
	r := F.Find(s.Super[ao:bo], -1).Subs
	rl := len(r)

	//if there are no substrings of that substring, we delete it
	if rl == 0 {
		return s.Delete(i)
	}

	//shift indicies of r to keep them relative to s.Super
	for _, v := range r {
		v[0] += ao
		v[1] += ao
	}

	// If there's only one substring in the refinement,
	//we can just set it and bail
	if rl == 1 {
		s.Subs[i] = r[0]
		return s
	}

	//We obsess over the small efficiency of avoiding copying cell i when
	//we move stuff around on some misguided hobgoblin of a principle.
	//That aside, below we create an r-sized hole starting at position i
	//so we have room to place the refinement
	ln := len(s.Subs)
	total := ln + rl - 1 //size needed
	s0, s1 := i+1, i+rl  //edge of r-gap, before and after, sans i itself
	if c := cap(s.Subs); c < total {
		sz := c + c/2
		if sz < total {
			sz = total
		}
		new := make([][]int, total, sz)
		copy(new[:i], s.Subs[:i])
		copy(new[s1:], s.Subs[s0:])
		s.Subs = new
	} else {
		//no need to resize, reslice and make a hole
		s.Subs = s.Subs[:total]
		copy(s.Subs[s1:], s.Subs[s0:ln])
	}

	//drop r into the hole
	copy(s.Subs[i:s1], r)
	return s
}

func (s *S) refine_filter(negate bool, M Matcher, F Finder) {
	//this could be faster but chances are that |s.Subs| << |s.Super|
	for i, v := range s.Subs {
		t := M.Match(s.Super[v[0]:v[1]])
		if negate {
			t = !t
		}
		if t {
			s.Refine(i, F)
		}
	}
}

//For each substring that M matches, refine based on F.
func (s *S) RefineIf(M Matcher, F Finder) *S {
	s.refine_filter(false, M, F)
	return s
}

//For each substring that M does not match, refine based on F.
func (s *S) RefineIfNot(M Matcher, F Finder) *S {
	s.refine_filter(true, M, F)
	return s
}

//Apply a finder to all substrings, refining based on result.
//See Refine for more details.
// The operation is inplace and returns itself for chaining.
func (s *S) RefineAll(F Finder) *S {
	//no matches to refine, skip a bunch of allocations
	if len(s.Subs) == 0 {
		return s
	}

	//we accumulate the results in an [][][]int that will be at most as long
	//as the length of the current number of substrings.
	ai, sz, acc := 0, 0, make([][][]int, len(s.Subs))
	for _, v := range s.Subs {
		d := v[0]
		//Skip over nil matches, implicitly deleting them
		if s := F.Find(s.Super[d:v[1]], -1).Subs; len(s) != 0 {
			//shift indicies based on start of original substring, d
			for _, ss := range s {
				ss[0] += d
				ss[1] += d
			}
			acc[ai] = s
			ai++
			sz += len(s)
		}
	}

	//all substrings nil'd, bail out before we have to allocate anything
	if len(acc) == 0 {
		for i := range s.Subs {
			s.Subs[i] = nil
		}
		s.Subs = s.Subs[:0]
		return s
	}

	//we've overwriting everything so we try to reuse s.Subs if possible
	if sz <= cap(s.Subs) {
		s.Subs = s.Subs[:sz]
	} else {
		s.Subs = make([][]int, sz)
	}
	start := 0
	for _, v := range acc {
		vl := len(v)
		copy(s.Subs[start:start+vl], v)
		start += vl
	}
	return s
}
